package pers.qianyu.month_202011.date_20201118;

import java.util.*;

/**
 * 18. 四数之和
 * https://leetcode-cn.com/problems/4sum/
 *
 * @author mizzle rain
 * @date 2020-11-18 17:03
 */
public class FourSum2 {
    /**
     * 不使用 set，进行手动去重
     */
    public List<List<Integer>> fourSum(int[] nums, int target) {
        int len = nums.length;
        if (len < 3) {
            return new ArrayList<>();
        }
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<>();
        for (int i = 0; i < len - 3; i++) {
            if (i != 0 && nums[i] == nums[i - 1]) {
                continue;
            }
            for (int j = i + 1; j < len - 2; j++) {
                if (j != i + 1 && nums[j] == nums[j - 1]) {
                    continue;
                }
                int a = nums[i] + nums[j];
                int left = j + 1, right = nums.length - 1;
                while (left < right) {
                    int leftNum = nums[left];
                    int rightNum = nums[right];
                    if (a + leftNum + rightNum > target) {
                        right--;
                    } else if (a + leftNum + rightNum < target) {
                        left++;
                    } else {
                        ArrayList<Integer> list = new ArrayList<>(Arrays.asList(
                                nums[i], nums[j], leftNum, rightNum));
                        res.add(list);
                        while (left < right && nums[left] == leftNum) {
                            left++;
                        }
                        while (left < right && nums[right] == rightNum) {
                            right--;
                        }
                    }
                }
            }
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = {-2, -1, -1, 1, 1, 2, 2};
        //int[] arr = {0, 0, 0, 0};
        int target = 0;
        System.out.println("arr = " + Arrays.toString(arr));
        List<List<Integer>> result = new FourSum2().fourSum(arr, target);
        System.out.println("result = " + result);
    }
}
